package com.tgy.back.tracking;

/**
 * @Author: tgy
 * @Date: 2020-11-02 09:29
 */
public class Queens {

    private int[] locals;

    private int kinds;

    public int queens(int n){

        locals = new int[n];

        find(0);
        return kinds;
    }

    public void printQueens() {

        for (int i = 0; i < locals.length; i++) {

            for (int j = 0; j < locals.length; j++) {

                if (locals[i] == j) {

                    System.out.print(" 1 ");
                }else {

                    System.out.print(" 0 ");
                }
            }
            System.out.println();
        }
        System.out.println("================");
    }

    private void find(int row) {

        if (row == locals.length) {

            kinds++;
            printQueens();
            return;
        }

        for (int col = 0; col < locals.length; col++) {

            if (isQueen(row,col)) {

                locals[row] = col;
                find(row + 1);
            }

        }

    }


    private boolean isQueen(int row, int col) {

        for (int i = 0; i < row; i++) {

            /**
             * 在同一列上面
             */
            if (locals[i] == col) {
                return false;
            }

            /**
             * 在同一斜线上面
             */
            if (row - i == Math.abs(col - locals[i])) {
                return false;
            }
        }

        return true;
    }
}
